package com.lw.leetcode.sort.c;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * 1383. 最大的团队表现值
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/15 17:54
 */
public class MaxPerformance {

    public static void main(String[] args) {
        MaxPerformance test = new MaxPerformance();

        // 60
//        int n = 6;
//        int[] speed = {2, 10, 3, 1, 5, 8};
//        int[] efficiency = {5, 4, 3, 9, 7, 2};
//        int k = 2;

        // 68
//        int n = 6;
//        int[] speed = {2, 10, 3, 1, 5, 8};
//        int[] efficiency = {5, 4, 3, 9, 7, 2};
//        int k = 3;

        // 72
        int n = 6;
        int[] speed = {2, 10, 3, 1, 5, 8};
        int[] efficiency = {5, 4, 3, 9, 7, 2};
        int k = 4;

        int i = test.maxPerformance(n, speed, efficiency, k);
        System.out.println(i);

    }

    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = ((long) efficiency[i] << 32) + speed[i];
        }
        Arrays.sort(arr);
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        long sum = 0;
        long max = 0;
        for (int i = n - 1; i >= 0; i--) {
            long l = arr[i];
            long a = l >> 32;
            int b = (int) l;
            if (queue.size() >= k) {
                sum -= queue.poll();
            }
            sum += b;
            max = Math.max(max, sum * a);
            queue.add(b);
        }
        return (int) (max % 1000000007);
    }

}
